#include<iostream>
#include<unordered_map>
#include<unordered_set>
using namespace std;

struct ListNode{
    int value;
    ListNode* next;
    ListNode(): value(0), next(nullptr) {}
    ListNode(int value) : value(value), next(nullptr){}
    ListNode(int value, ListNode *next) : value(value), next(next) {}
};

//----------------------------------------------------------------
// 实现链表的逆置
// 双指针
class Solution{
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prep = nullptr;
        while(head) {
            ListNode* tmp = head->next;
            head->next = prep;
            prep = head;
            head = tmp;
        }
    }
};

// 递归
class Solution{
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }
    ListNode* reverse(ListNode* pre, ListNode* cur) {
        if (!cur) return pre;
        ListNode* nextNode = cur->next;
        cur->next = pre;
        return reverse(cur, nextNode);
    }
};

//----------------------------------------------------------------
// 判断单链表中是否存在环
// 快慢指针
class Soluthion{
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        // 注意短路效应
        while(fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;

    }
};
// 哈希表的方式
class Soluthion{
    bool hasCycle(ListNode* head) {
        if (!head || !head->next) return false;
        unordered_set<ListNode*> visited;
        while(head) {
            if (visited.count(head)) {
                return true;
            }
            visited.insert(head);
            head = head->next;
        }
        return false;

    }
};

//----------------------------------------------------------------
// 判断单链表中是否存在环---并判断环在哪里
// 快慢指针
class Soluthion{
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;

        // 注意短路效应
        while(fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* cur = head;
                while(cur != slow) {
                    cur = cur->next;
                    slow = cur->next;
                }
                return cur;
            }
        }
        return nullptr;

    }
};

// 哈希表的方式
class Soluthion{
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) return nullptr;
        unordered_set<ListNode*> visited;
        while(head) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;

    }
};

//----------------------------------------------------------------
// 单链表相交，如何求交点（已知相交）-----模拟环形链表
// 双指针
class Soluthion {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* listA = headA;
        ListNode* listB = headB;
        while (listA != listB) {
            listA = listA != nullptr ? listA->next : headB;
            listB = listB != nullptr ? listB->next : headA;
        }
        return listA;
    }
};
//----------------------------------------------------------------
// 写出链表的删除一个节点的程序-----虚拟头节点
void deleteNodeAtIndex(ListNode* head, int index) {
    ListNode* preNode = new ListNode(0, head); // 虚拟头节点----要删除节点的上一个节点
    while(index-- && preNode != nullptr && preNode->next != nullptr) {
        preNode = preNode->next;
    }
    if (index > 0) return;  // 没有找到
    ListNode* tmp = preNode->next;
    preNode = preNode->next->next;
    delete tmp;
    return;
}

//----------------------------------------------------------------
// 用普通算法实现两个有序链表的合并
// 法一： 虚拟头节点---新链表
// 思路：创建一个新的虚拟头节点，同时遍历两个新链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        ListNode* dummyHead = new ListNode(0);
        ListNode* pre = dummyHead;
        while(l1 && l2) {
            if (l1->value < l2->value) {
                pre->next = l1;
                // pre->next = new ListNode(l1->value);
                l1 = l1->next;
            } else {
                pre->next = l2;
                // pre->next = new ListNode(l2->value);
                l2 = l2->next;
            }
            pre = pre->next;
        }
        pre->next = (!l1) ? l2 : l1;
        return dummyHead->next;
    }
};
// 法二：递归实现
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->value < l2->value) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

int main(int argc, char **argv){
    return 0;
}